{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Dict\n",
    "memo: Dict[int, int] = {0: 0, 1: 1}  # our base cases\n",
    "\n",
    "def fib3(n: int) -> int:\n",
    "    if n not in memo: \n",
    "        memo[n] = fib3(n - 1) + fib3(n - 2)  # memoization\n",
    "    return memo[n]\n",
    "\n",
    "fib3(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import lru_cache\n",
    "\n",
    "@lru_cache(maxsize=None)\n",
    "def fib4(n: int) -> int:  # same definition as fib2()\n",
    "    if n < 2:  # base case\n",
    "        return n\n",
    "    return fib4(n - 2) + fib4(n - 1)  # recursive case\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib5(n: int) -> int:\n",
    "    if n == 0: return n  # special case\n",
    "    last: int = 0  # initially set to fib(0)\n",
    "    next: int = 1  # initially set to fib(1)\n",
    "    for _ in range(1, n):\n",
    "        last, next = next, last + next\n",
    "    return next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Generator\n",
    "\n",
    "def fib6(n: int) -> Generator[int, None, None]:\n",
    "    yield 0  # special case\n",
    "    if n > 0:\n",
    "        yield 1  # special case\n",
    "    last: int = 0  # initially set to fib(0)\n",
    "    next: int = 1  # initially set to fib(1)\n",
    "    for _ in range(1, n):\n",
    "        last, next = next, last + next\n",
    "        yield next  # main generation step\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hanoi(a, b, c, n):\n",
    "    if (n == 1):\n",
    "        print(f\"{a} -> {c}\")\n",
    "    else:\n",
    "        hanoi(a, c, b, n-1)\n",
    "        print(f\"{a} -> {c}\")\n",
    "        hanoi(b, a, c, n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from enum import Enum\n",
    "from typing import List, NamedTuple, Callable, Optional\n",
    "import random\n",
    "from math import sqrt\n",
    "# from generic_search import dfs, bfs, node_to_path, astar, Node\n",
    "\n",
    "\n",
    "class Cell(str, Enum):\n",
    "    EMPTY = \" \"\n",
    "    BLOCKED = \"X\"\n",
    "    START = \"S\"\n",
    "    GOAL = \"G\"\n",
    "    PATH = \"*\"\n",
    "\n",
    "\n",
    "class MazeLocation(NamedTuple):\n",
    "    row: int\n",
    "    column: int\n",
    "\n",
    "\n",
    "class Maze:\n",
    "    def __init__(self, rows: int = 10, columns: int = 10, sparseness: float = 0.2, start:\n",
    "                 MazeLocation = MazeLocation(0, 0), goal: MazeLocation = MazeLocation(9, 9)) -> None:\n",
    "        # initialize basic instance variables\n",
    "        self._rows: int = rows\n",
    "        self._columns: int = columns\n",
    "        self.start: MazeLocation = start\n",
    "        self.goal: MazeLocation = goal\n",
    "        # fill the grid with empty cells\n",
    "        self._grid: List[List[Cell]] = [\n",
    "            [Cell.EMPTY for c in range(columns)] for r in range(rows)]\n",
    "        # populate the grid with blocked cells\n",
    "        self._randomly_fill(rows, columns, sparseness)\n",
    "        # fill the start and goal locations in\n",
    "        self._grid[start.row][start.column] = Cell.START\n",
    "        self._grid[goal.row][goal.column] = Cell.GOAL\n",
    "\n",
    "    def _randomly_fill(self, rows: int, columns: int, sparseness: float):\n",
    "        for row in range(rows):\n",
    "            for column in range(columns):\n",
    "                if random.uniform(0, 1.0) < sparseness:\n",
    "                    self._grid[row][column] = Cell.BLOCKED\n",
    "\n",
    "    def __str__(self) -> str:\n",
    "        output: str = \"\"\n",
    "        for row in self._grid:\n",
    "            output += \"\".join([c.value for c in row]) + \"\\n\"\n",
    "        return output\n",
    "\n",
    "\n",
    "maze: Maze = Maze(sparseness=0.3)\n",
    "print(maze)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Generic, TypeVar\n",
    "\n",
    "T =TypeVar('T')\n",
    "\n",
    "class Stack(Generic[T]):\n",
    "    def __init__(self) -> None:\n",
    "        self._container: List[T] = []\n",
    "\n",
    "    @property\n",
    "    def empty(self) -> bool:\n",
    "        return not self._container  # not is true for empty container\n",
    "\n",
    "    def push(self, item: T) -> None:\n",
    "        self._container.append(item)\n",
    "\n",
    "    def pop(self) -> T:\n",
    "        return self._container.pop()  # LIFO\n",
    "\n",
    "    def __repr__(self) -> str:\n",
    "        return repr(self._container)\n",
    "\n",
    "stack:Stack=Stack(int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Generic, TypeVar\n",
    "\n",
    "T =TypeVar('T')\n",
    "\n",
    "class Node(Generic[T]):\n",
    "    def __init__(self, state: T, parent: Optional[Node], cost: float = 0.0, heuristic: \n",
    "     float  = 0.0) -> None:\n",
    "      self.state: T = state\n",
    "      self.parent: Optional[Node] = parent\n",
    "      self.cost: float = cost\n",
    "      self.heuristic: float = heuristic\n",
    "\n",
    "    def __lt__(self, other: Node) -> bool:\n",
    "        return (self.cost + self.heuristic) < (other.cost + other.heuristic)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from queue import PriorityQueue\n",
    "\n",
    "\n",
    "def astar(initial: T, goal_test: Callable[[T], bool], successors: Callable[[T],\n",
    " List[T]], heuristic: Callable[[T], float]) -> Optional[Node[T]]:\n",
    "    # frontier is where we've yet to go\n",
    "    frontier: PriorityQueue[Node[T]] = PriorityQueue()\n",
    "    frontier.push(Node(initial, None, 0.0, heuristic(initial)))\n",
    "    # explored is where we've been\n",
    "    explored: Dict[T, float] = {initial: 0.0}\n",
    "\n",
    "    # keep going while there is more to explore\n",
    "    while not frontier.empty:\n",
    "        current_node: Node[T] = frontier.pop()\n",
    "        current_state: T = current_node.state\n",
    "        # if we found the goal, we're done\n",
    "        if goal_test(current_state):\n",
    "            return current_node\n",
    "        # check where we can go next and haven't explored\n",
    "        for child in successors(current_state):\n",
    "            # 1 assumes a grid, need a cost function for more sophisticated apps\n",
    "            new_cost: float = current_node.cost + 1  \n",
    "            if child not in explored or explored[child] > new_cost:\n",
    "                explored[child] = new_cost\n",
    "                frontier.push(Node(child, current_node, new_cost, heuristic(child)))\n",
    "    return None  # went through everything and never found goal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "N(2)\n",
      "N(1)\n",
      "N(3)\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "    def __str__(self) -> str:\n",
    "        return f'N({self.val})'\n",
    "\n",
    "    def __repr__(self) -> str:\n",
    "        return self.__str__()\n",
    "\n",
    "def preorder(root):\n",
    "    if root == None:\n",
    "        return\n",
    "    print(root)\n",
    "    preorder(root.left)\n",
    "    preorder(root.right)\n",
    "\n",
    "\n",
    "root = Node(2)\n",
    "root.left = Node(1)\n",
    "root.right = Node(3)\n",
    "preorder(root)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.3"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "4c2b8563932708ac4f64e3bc4797ea8eb43fc7530baa7f01daadf5b46d7b1fd4"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
